package club.xiaojiawei.array;

import java.util.Arrays;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/24/22 5:23 PM
 * @question 1356. 根据数字二进制下 1 的数目排序
 * @description 给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
 * 如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
 * 请你返回排序后的数组。
 */
public class SortByBits1356 {

    public static void main(String[] args) {
        SortByBits1356 test = new SortByBits1356();
        int[] result = test.sortByBits(new int[]{1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1});
        System.out.println(Arrays.toString(result));
    }

    /**
     * 计数
     * @param arr
     * @return
     */
    public int[] sortByBits(int[] arr) {
//        Arrays.sort(arr);
//        countSort(arr);
        quickSort(0, arr.length - 1, arr);
//        shellSort(arr);
        int[][] bucket = new int[14][arr.length];
        int[] index = new int[14];
        int num;
        for (int i : arr) {
            num = Integer.bitCount(i);
            bucket[num][index[num]++] = i;
        }
        num = 0;
        for (int i = 0; i < 14; i++) {
            for (int j = 0; j < index[i]; j++){
                arr[num++] = bucket[i][j];
            }
        }
        return arr;
    }

    int[] bits;

    /**
     * 民间
     * @param arr
     * @return
     */
    public int[] sortByBits2(int[] arr) {
        int len = arr.length;
        this.bits = new int[len];
        for(int i = 0; i < len; i++){
            bits[i] = Integer.bitCount(arr[i]);
        }

        quickSort(arr, 0, len - 1);//使用改进的快排，因为快排是稳定排序
        return arr;
    }
    private void quickSort(int[] arr, int lo, int hi){
        if(lo < hi){
            int lt = lo, i = lo + 1, rt = hi;
            int k = bits[lt];
            while(i <= rt){
                if(bits[i] < k){
                    exch(bits, lt, i);
                    exch(arr, lt++, i++);
                }else if(bits[i] > k){
                    exch(bits, rt, i);
                    exch(arr, rt--, i);
                }else{
                    i++;
                }
            }
            for(i = lt + 1; i <= rt; i++){
                for(int j = i; j >= lt + 1; j--){
                    if(arr[j] < arr[j - 1]){
                        exch(arr, j, j - 1);
                    }else break;
                }
            }
            quickSort(arr, lo, lt - 1);
            quickSort(arr, rt + 1, hi);
        }

    }
    private void exch(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void countSort(int[] arr){
        int max = arr[0];
        int min = arr[0];
        for (int k : arr) {
            if (k > max) {
                max = k;
            } else if (k < min) {
                min = k;
            }
        }
        int[] ints = new int[max - min + 1];
        for (int k : arr) {
            ints[k - min]++;
        }
        int index = 0;
        for (int i = 0; i < ints.length; i++) {
            for (int j = 0; j < ints[i]; j++) {
                arr[index++] = min + i;
            }
        }
    }

    public static void quickSort(int l, int r, int[] arr){
        if (l>=r){
            return;
        }
        int left=l;
        int right=r;
        int benchmark=arr[l];
        int temp;
        while (true){
            while (arr[r]>=benchmark&&l<r){
                r--;
            }
            while (arr[l]<=benchmark&&l<r){
                l++;
            }
            if (r==l){
                arr[left]=arr[r];
                arr[r]=benchmark;
                break;
            }else {
                temp=arr[r];
                arr[r]=arr[l];
                arr[l]=temp;
            }
        }
        quickSort(left,r-1,arr);
        quickSort(l+1,right,arr);
    }

    public static void shellSort(int[] arr) {
        //增量gap, 并逐步的缩小增量
        for(int gap=arr.length/2;gap>0;gap/=2){
            //从第gap个元素,逐个对其所在的组进行直接插入排序
            for (int i = gap; i < arr .length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        //移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    //当退出while后,就给temp找到插入的位置
                    arr[j] = temp;
                }
            }
        }
    }
}
